package org.apache.commons.graph.algorithms.shortestpath

import org.apache.commons.graph.CommonsGraph.findShortestPath
import org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph
import org.apache.commons.graph.GraphException
import org.apache.commons.graph.Path
import org.apache.commons.graph.weight.WeightedPath
import org.apache.commons.graph.algorithms.shortestpath.exception.PathNotFoundException
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.*
import org.apache.commons.graph.weight.OrderedMonoid
import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations
import org.junit.Assert
import org.junit.BeforeClass
import org.junit.Test
import java.util.*
import kotlin.math.max
import kotlin.test.assertEquals

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

class BidirDijkstraTestCase {
    @Test
    fun testCompareToUnidirectional() {
        // It is hard to get unidirectional Dijkstra's algorithm wrong;
        // therefore compare a sequence of outputs.
        val r = Random()

        for (ii in 0..<TIMES) {
            val s = vertices!![r.nextInt(vertices!!.size)]
            var t: BaseLabeledVertex

            do {
                t = vertices!![r.nextInt(vertices!!.size)]
            } while (s == t)

            val pathUni: WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
                findShortestPath(graph!!)
                    .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                    .from(s)
                    .to(t)
                    .applyingDijkstra(weightOperations!!)

            val pathBi: WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
                findShortestPath(graph!!)
                    .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                    .from(s)
                    .to(t)
                    .applyingBidirectionalDijkstra(weightOperations!!)

            assertEquals(pathUni.size, pathBi.size)
            assertEquals(pathUni.weight, pathBi.weight, EPSILON)
        }
    }

    /**
     * Test Graph and Dijkstra's solution can be seen on
     * [](http://en.wikipedia.org/wiki/Dijkstra's_algorithm>Wikipedia</a>
     ) */
    @Test
    fun testFindShortestPathAndVerify() {
        val graph =
            DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        // building Graph
        val one = BaseLabeledVertex("1")
        val two = BaseLabeledVertex("2")
        val three = BaseLabeledVertex("3")
        val four = BaseLabeledVertex("4")
        val five = BaseLabeledVertex("5")
        val six = BaseLabeledVertex("6")

        graph.addVertex(one)
        graph.addVertex(two)
        graph.addVertex(three)
        graph.addVertex(four)
        graph.addVertex(five)
        graph.addVertex(six)

        graph.addEdge(one, BaseLabeledWeightedEdge("1 -> 6", 14.0), six)
        graph.addEdge(one, BaseLabeledWeightedEdge("1 -> 3", 9.0), three)
        graph.addEdge(one, BaseLabeledWeightedEdge("1 -> 2", 7.0), two)

        graph.addEdge(two, BaseLabeledWeightedEdge("2 -> 3", 10.0), three)
        graph.addEdge(two, BaseLabeledWeightedEdge("2 -> 4", 15.0), four)

        graph.addEdge(three, BaseLabeledWeightedEdge("3 -> 6", 2.0), six)
        graph.addEdge(three, BaseLabeledWeightedEdge("3 -> 4", 11.0), four)

        graph.addEdge(four, BaseLabeledWeightedEdge("4 -> 5", 6.0), five)
        graph.addEdge(six, BaseLabeledWeightedEdge("6 -> 5", 9.0), five)

        // expected path
        val expected = InMemoryWeightedPath(one, five, DoubleWeightBaseOperations, BaseWeightedEdge())

        expected.addConnectionInTail(one, BaseLabeledWeightedEdge("1 -> 3", 9.0), three)
        expected.addConnectionInTail(three, BaseLabeledWeightedEdge("3 -> 6", 2.0), six)
        expected.addConnectionInTail(six, BaseLabeledWeightedEdge("6 -> 5", 9.0), five)

        // actual path
        val actual: Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> =
            findShortestPath(graph)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .from(one)
                .to(five)
                .applyingBidirectionalDijkstra(DoubleWeightBaseOperations)

        // assert!
        Assert.assertEquals(expected, actual)
    }

    @Test(expected = PathNotFoundException::class)
    fun testNotConnectGraph() {
        val graph =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        graph.addVertex(a)
        graph.addVertex(b)

        // the actual weighted path
        findShortestPath(graph)
            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
            .from(a)
            .to(b)
            .applyingBidirectionalDijkstra(DoubleWeightBaseOperations)
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        // the actual weighted path
//        findShortestPath(null as Graph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(null)
//            .to(null)
//            .applyingBidirectionalDijkstra(DoubleWeightBaseOperations)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullMonoid() {
//        val graph =
//            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()
//
//        val a = BaseLabeledVertex("a")
//        val b = BaseLabeledVertex("b")
//        graph.addVertex(a)
//        graph.addVertex(b)
//
//        // the actual weighted path
//        findShortestPath(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(a)
//            .to(b)
//            .applyingBidirectionalDijkstra(null)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullVertices() {
//        val graph =
//            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()
//
//        // the actual weighted path
//        findShortestPath(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(null)
//            .to(null)
//            .applyingBidirectionalDijkstra(DoubleWeightBaseOperations)
//    }

    @Test
    fun testVerifyThreeNodePath() {
        val graph =
            DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        // building Graph
        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        val c = BaseLabeledVertex("c")

        graph.addVertex(a)
        graph.addVertex(b)
        graph.addVertex(c)

        graph.addEdge(a, BaseLabeledWeightedEdge("a -> b", 14.0), b)
        graph.addEdge(b, BaseLabeledWeightedEdge("b -> c", 10.0), c)

        // expected path
        val expected =
            InMemoryWeightedPath(a, c, DoubleWeightBaseOperations, BaseWeightedEdge())

        expected.addConnectionInTail(a, BaseLabeledWeightedEdge("a -> b", 14.0), b)
        expected.addConnectionInTail(b, BaseLabeledWeightedEdge("b -> c", 10.0), c)

        // actual path
        val actual: Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> =
            findShortestPath(graph)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .from(a)
                .to(c)
                .applyingBidirectionalDijkstra(DoubleWeightBaseOperations)

        // assert!
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun testVerifyTwoNodePath() {
        val graph =
            DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        // building Graph
        val one = BaseLabeledVertex("1")
        val two = BaseLabeledVertex("2")

        graph.addVertex(one)
        graph.addVertex(two)

        graph.addEdge(one, BaseLabeledWeightedEdge("1 -> 2", 14.0), two)

        // expected path
        val expected =
            InMemoryWeightedPath(one, two, DoubleWeightBaseOperations, BaseWeightedEdge())

        expected.addConnectionInTail(one, BaseLabeledWeightedEdge("1 -> 2", 14.0), two)

        // actual path
        val actual: Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> =
            findShortestPath(graph)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .from(one)
                .to(two)
                .applyingBidirectionalDijkstra(DoubleWeightBaseOperations)

        // assert!
        Assert.assertEquals(expected, actual)
    }

    companion object {
        private const val TIMES = 10
        private const val NODES = 5000
        private const val EDGES = 100000
        private const val EPSILON = 1.0e-6

        private var graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>? = null

        private var vertices: MutableList<BaseLabeledVertex>? = null

        private var weightOperations: OrderedMonoid<Double>? = null

        @JvmStatic
        @BeforeClass
        fun setUp(): Unit {
            weightOperations = DoubleWeightBaseOperations

            graph = newDirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() {
                var r: Random = Random()

                fun addEdge(src: BaseLabeledVertex, dst: BaseLabeledVertex): Boolean {
                    try {
                        addEdge(
                            BaseLabeledWeightedEdge(
                                String.format("%s -> %s", src, dst),
                                10.0 * r.nextDouble() + 1.0
                            )
                        ).from(src).to(dst)
                        return true
                    } catch (e: GraphException) {
                        // ignore duplicate edge exceptions
                        return false
                    }
                }

                override fun connect() {
                    vertices = mutableListOf()
                    for (i in 0..<NODES) {
                        val v = BaseLabeledVertex(i.toString())
                        addVertex(v)
                        vertices!!.add(v)
                    }

                    // form a connected graph
                    for (i in 0..<NODES - 1) {
                        addEdge(vertices!!.get(i), vertices!!.get(i + 1))
                    }

                    addEdge(vertices!!.get(NODES - 1), vertices!!.get(0))

                    // we have already created #NODES edges
                    val maxEdges = max(0.0, (EDGES - NODES).toDouble()).toInt()
                    for (i in 0..<maxEdges) {
                        while (!addEdge(vertices!!.get(r.nextInt(NODES)), vertices!!.get(r.nextInt(NODES)))) {
                            // do nothing
                        }
                    }
                }
            })
        }
    }
}
